//给你一个 互不相同 的整数数组，其中 locations[i] 表示第 i 个城市的位置。同时给你 start，finish 和 fuel 分别表示出发城市
//、目的地城市和你初始拥有的汽油总量 
//
// 每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足 j != i 且 0 <= j < locations.length ，并移动到城市 
//j 。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|，|x| 表示 x 的绝对值。 
//
// 请注意， fuel 任何时刻都 不能 为负，且你 可以 经过任意城市超过一次（包括 start 和 finish ）。 
//
// 请你返回从 start 到 finish 所有可能路径的数目。 
//
// 由于答案可能很大， 请将它对 10^9 + 7 取余后返回。 
//
// 
//
// 示例 1： 
//
// 
//输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
//输出：4
//解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
//1 -> 3
//1 -> 2 -> 3
//1 -> 4 -> 3
//1 -> 4 -> 2 -> 3
// 
//
// 示例 2： 
//
// 
//输入：locations = [4,3,1], start = 1, finish = 0, fuel = 6
//输出：5
//解释：以下为所有可能的路径：
//1 -> 0，使用汽油量为 fuel = 1
//1 -> 2 -> 0，使用汽油量为 fuel = 5
//1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
//1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
//1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5
// 
//
// 示例 3： 
//
// 
//输入：locations = [5,2,1], start = 0, finish = 2, fuel = 3
//输出：0
//解释：没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。 
//
// 
//
// 提示： 
//
// 
// 2 <= locations.length <= 100 
// 1 <= locations[i] <= 10⁹ 
// 所有 locations 中的整数 互不相同 。 
// 0 <= start, finish < locations.length 
// 1 <= fuel <= 200 
// 
// Related Topics记忆化搜索 | 数组 | 动态规划 
//
// 👍 79, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;

class CountAllPossibleRoutes {
    public static void main(String[] args) {
        Solution solution = new CountAllPossibleRoutes().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*int mod = 1000000007;
        int[][] cache;  // 一维表示起点，二维表示剩余燃油，cache[i][j]表示从i开始，使用j燃油能到达目的的路径

        // 记忆化DFS
        public int countRoutes(int[] locations, int start, int finish, int fuel) {
            int n = locations.length;
            cache = new int[n][fuel + 1];
            for (int i = 0; i < n; i++) {
                Arrays.fill(cache[i], -1);
            }

            return dfs(locations, start, finish, fuel);
        }

        private int dfs(int[] lt, int s, int e, int fuel) {
            // 查看缓存
            if (cache[s][fuel] != -1) {
                return cache[s][fuel];
            }

//            // 如果燃油为0，起始不是终点
//            if (fuel == 0 && s != e) {
//                cache[s][fuel] = 0;
//                return 0;
//            }
//
//            // 如果在剩余的fuel下，没有地方可以到达
//            boolean hasNext = false;
//            for (int i = 0; i < lt.length; i++) {
//                if (i != s) {
//                    int need = Math.abs(lt[s] - lt[i]);
//                    if (fuel >= need) {
//                        hasNext = true;
//                        break;
//                    }
//                }
//            }
//
//            if (fuel != 0 && !hasNext) {
//                cache[s][fuel] = s == e ? 1 : 0;
//                return cache[s][fuel];
//            }

            // 以上剪枝可以简化为如下:如果一条路径燃油无法到达终点，那么无论中间走多少条路径，也不会改变 fuel < need
            int need = Math.abs(lt[e] - lt[s]);
            if (fuel < need) {
                cache[s][fuel] = 0;
                return 0;
            }

            // 进行DFS搜索
            int cnt = s == e ? 1 : 0;
            for (int i = 0; i < lt.length; i++) {
                if (i != s) {
                    need = Math.abs(lt[s] - lt[i]);
                    if (fuel >= need) {
                        cnt += dfs(lt, i, e, fuel - need);
                        cnt %= mod;
                    }
                }
            }

            cache[s][fuel] = cnt;
            return cnt;
        }*/

        public int countRoutes(int[] locations, int start, int finish, int fuel) {
            int mod = 1000000007;
            int n = locations.length;
            int[][] dp = new int[n][fuel + 1];  // 表示从i开始，在j燃油的情况下，到达目的地的路径

            // 初始化，终点不管多少燃油都可以到达
            for (int i = 0; i <= fuel; i++) dp[finish][i] = 1;

            for (int curFuel = 0; curFuel <= fuel; curFuel++) {
                for (int i = 0; i < n; i++) {
                    //燃油不足以支撑到达到终点城市
                    if (Math.abs(locations[finish] - locations[i]) > curFuel) continue;

                    // 进行枚举
                    for (int k = 0; k < n; k++) {
                        if (i != k) {
                            int need = Math.abs(locations[k] - locations[i]);
                            if (curFuel >= need) {
                                dp[i][curFuel] += dp[k][curFuel - need];
                                dp[i][curFuel] %= mod;
                            }
                        }
                    }
                }
            }

            return dp[start][fuel];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
